//https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
//二叉树遍历
//编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 
//例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。
//建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (*pi >= n || a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	else
	{
		BTNode* root = BuyNode(a[*pi]);
		(*pi)++;
		root->left = BinaryTreeCreate(a, n, pi);
		root->right = BinaryTreeCreate(a, n, pi);
		return root;
	}
}

void InOrder(BTNode* root)
{
    if(root == NULL)
    {
        return;
    }
    else 
    {
        InOrder(root->left);
        printf("%c ", root->data);
        InOrder(root->right);
    }
}

int main() {
    char s[101];
    scanf("%s", s);
    int n = strlen(s);
    int i = 0;
    BTNode* root = BinaryTreeCreate(s, n, &i);
    InOrder(root);

    return 0;
}